COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\magnification\magstephalf
C00010 ENDMK
C⊗;
\magnification\magstephalf
\input macro.tex
\def\today{\ifcase\month\or
  January\or February\or March\or April\or May\or June\or
  July\or August\or September\or October\or November\or December\fi
  \space\number\day, \number\year}
\baselineskip 14pt
\rm
\line{\sevenrm a16.tex[162,phy] \today\hfill}

\parskip 5pt
\bigskip
\line{\bf Carousels, Horses, Children, and Trees\hfil}

\smallskip
Cayley's Theorem states that the number of unrooted trees on $n$~vertices
is $n↑{n-2}$. My purpose is to present and, I~hope, motivate an
elementary proof.

Let $T↓n$ be the number of labeled unrooted trees on $n≥2$ vertices numbered
1 to~$n$. 
There are ${n\choose 2}$ possible edges, of which $n-1$ occur in each tree.
By symmetry, the number of trees containing a particular edge,
say $(1,2)$, is ${n-1\over{n\choose 2}}\,T↓n={2\over n}\,T↓n$. Removing
that edge leaves a tree of size $a≥1$ containing vertex~1, and a tree of size
$b=n-a≥1$ containing vertex~2; there are
$\sum↓{a+b=n}\,{n-2\choose a-1}T↓aT↓b$ such forests, in one-to-one correspondence
with the ${2\over n}T↓n$ trees containing $(1,2)$, so
$${2\over n}\;T↓n=(n-2)!\,\sum↓{\scriptstyle a+b=n\atop
\scriptstyle a,b≥1}\;{T↓a\over (a-1)!}\;{T↓b\over (b-1)!}\,.\eqno(1)$$
This recurrence is formidable. A counting argument with no obvious relation
to trees, though, shows that $T↓n=n↑{n-2}$ satisfies the recurrence.

A carousel has $n$ horses, numbered consecutively from~1 to~$n$. Each of
a sequence of $n-k$ arriving children in turn gets on the carousel beside
an arbitrary horse, then walks from horse to horse, mounting the first
vacant horse, where horse number~1 follows horse number~$n$.
A~{\sl boarding sequence\/} specifies for each child where the child
first gets on the carousel.
There are $n↑{n-k}$ boarding sequences;
each leaves $k$~horses vacant. By the obvious circular symmetry of carousels,
a~fraction $k/n$ of the boarding sequences, $k\,n↑{n-k-1}$ of them,
leave the $n↑{\rm th}$~horse, or any particular horse, vacant.

If the carousel operator sets barriers after the $a↑{\rm th}$~horse and
the~$n↑{\rm th}$, directing children from the $a↑{\rm th}$ to the first
and from the $n↑{\rm th}$ to the $a+1↑{\rm st}$, this in effect divides
the  carousel into two smaller ones of sizes~$a$ and $n-a$. A~boarding
sequence leaves horses~$a$ and~$n$ vacant if and only if it leaves them
vacant on the carousel with barriers, because in either case no child
is affected by the barriers.

More generally, the carousel can be divided into $k$~minicarousels of sizes
$a↓1,a↓2,a↓3,\ldots,a↓k$; a~boarding sequence leaves the last horse in
each minicarousel vacant if and only if it leaves them vacant on the undivided
carousel. There are
$${n-k\choose a↓1-1,a↓2-1,\ldots,a↓k-1}
\,\prod↓i a↓i↑{a↓i-2}
=(n-k)!\,\prod↓i\,{a↓i↑{a↓i-2}\over (a↓i-1)!}\eqno(2)$$
such boarding sequences, because $a↓i-1$ children must board the $i↑{\rm th}$
minicarousel.

By use of the idea of barriers and minicarousels, we can see that the
$k\,n↑{n-k-1}$
boarding sequences that leave the $n↑{\rm th}$~horse vacant can be partitioned
and counted according to the spacing between the $k$~vacancies remaining, so
$$kn↑{n-k-1}=(n-k)!\sum↓{\scriptstyle a↓1+a↓2+\cdots +a↓k=n\atop\scriptstyle
a↓i≥1}\,\prod↓i\,{a↓i↑{a↓i-2}\over (a↓i-1)!}\,.\eqno(3)$$
In particular, for $k=2$,
$$2n↑{n-3}=(n-2)!\sum↓{\scriptstyle a+b=n\atop\scriptstyle a,b≥1}\,
{a↑{a-2}\over (a-1)!}\;{b↑{b-2}\over (b-1)!}\,,$$
the same as the tree recurrence with $T↓n=n↑{n-2}$. 

Generalizing again, the number of forests on $n$~vertices consisting
of $k$~trees, each containing one specified vertex, is
$$\eqalignno{
\sum↓{\scriptstyle a↓1+a↓2+\cdots +a↓k=n\atop\scriptstyle a↓i≥1}
&\left((n-k)!\left/\prod↓{1≤i≤k}(a↓i-1)!\right.\right)\prod T↓{a↓i}\cr
\noalign{\smallskip}
&=(n-k)!\sum↓{\scriptstyle a↓1+a↓2+\cdots +a↓k=n\atop\scriptstyle a↓i≥1}
{a↓i↑{a↓i-2}\over (a↓i-1)!}=k\,n↑{n-k-1}&(4)\cr}$$

Historically, (1) and (3) are well known identities; see [$\;$] for a
variety of proofs of~(3), using higher level mathematics than is used
in the derivation above. Equation~(4) is due to Cayley; I~thank the
referee for observing that it follows from~(3).
Computer programmers may notice a similarity between carousels and hashing
algorithms with open addresses and linear probing [$\;$].

\bigskip
\noindent
{\bf Questions:}

\smallskip
\disleft 20pt:$\bullet$:
How far must the $n-1↑{\rm st}$ child go to find a vacant
horse, on the average?

\smallskip
\disleft 20pt:$\bullet$:
What is the probability that the $n-1↑{\rm st}$ child and the $n↑{\rm th}$ ride
adjacent horses?

\smallskip
\disleft 20pt::
$\bigl[$Answer: $\left({n-1\over n}\right)↑{n-3}\approx {1\over e}$.$\bigr]$

\smallskip
\disleft 20pt:$\bullet$:
Show that any permutation of a boarding sequence leads to 
occupancy of the same set of horses.


\bigskip
\parindent0pt
\copyright 1987 Robert W. Floyd.
First draft (not published)
June 1, 1987.
%revised date;
%subsequently revised.

\bye